This study evaluates the safety, tolerance, and effectiveness of combination chemotherapy (adriamycin, bleomycin +/- vincristine) and either dideoxyinosine (ddI) or dideoxycytidine (ddC) in patients with AIDS-related Karposi's Sarcoma.